package Week2;

import java.util.*;

public class Day10 {
}

//牛客:OR26:最长回文子串
class Solution5 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */

    //中心扩展法
    public int getLongestPalindrome (String A) {
        // write code here
        int len = 1;
        for(int i = 0; i < A.length(); i++){
            len = Math.max(len , Math.max(fun(A, i, i),fun(A, i, i + 1)));
        }
        return len;
    }

    public int fun(String A, int left , int right){
        while(left >= 0 && right < A.length() && A.charAt(left) == A.charAt(right)){
            left--;
            right++;
        }
        return right - left - 1;
    }
}

//牛客:DP30:买卖股票的最好时机(一)
class Main7 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }

        int ret = 0;
        int min = arr[0];
        for(int i = 0; i < n; i++){
            min = Math.min(min,arr[i]);
            ret = Math.max(ret,arr[i] - min);
        }
        System.out.println(ret);
    }
}

//牛客:DP13[NOIP2002 普及组]:过河卒
class Main8 {
    static boolean[][] visits;
    static int[] dx = {-1,-2,-2,-1,1,2,2,1};
    static int[] dy = {-2,-1,1,2,2,1,-1,-2};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();
        visits = new boolean[22][22];

        //将马能走到的地方进行标记
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
                visits[nx][ny] = true;
            }
        }
        visits[x][y] = true;

        long[][] dp = new long[n+1][m+1];
        dp[0][0] = 1;
        //在第一列和第一行的所以位置位置只有一种到达路线，如果它的前面被标记了，那么后面就都不能走到了
        for(int i = 1; i <= n; i++){
            if(visits[i][0]){
                dp[i][0] = 0;
            }else{
                dp[i][0] = dp[i-1][0];
            }
        }

        for(int j = 1; j <= m; j++){
            if(visits[0][j]){
                dp[0][j] = 0;
            }else{
                dp[0][j] = dp[0][j-1];
            }
        }

        //确定到达每个位置的所以路线
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(!visits[i][j]){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}